#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef pair<long long, int> PLI;
const int mod = 1e9 + 7;

long long qmi(long long x, int n)
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    if (multiplier == 1) return move(nums);

    priority_queue<PLI, vector<PLI>, greater<PLI>> pq;
    int mx = 0, n = nums.size();
    for (int i = 0; i < nums.size(); i++)
    {
        mx = max(mx, nums[i]);
        pq.emplace(nums[i], i);
    }

    while (k && pq.top().first < mx)
    {
        auto [num, i] = pq.top();
        pq.pop();
        num *= multiplier;
        pq.emplace(num, i);
        k--;
    }

    for (int i = 0; i < n; i++)
    {
        auto [num, j] = pq.top();
        pq.pop();

        nums[j] = num % mod * qmi(multiplier, k / n + (i < k% n)) % mod;
    }

    return nums;
}